/**
 * @Author Fizz Pu
 * @Date 2020/10/22 下午5:01
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

/**
 * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。
 * 请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
 *
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

// 抽象这个问题看，就是把n分成m个整数之和，让每个加数之积最大
// 1. 暴力法可以解决吗？每个加数都有1到1-n选择，共有m个加数，时间复杂度O(n ** m)
// 2. 可以递归的解决吗？n分成i 和 n - i, 再分i和n-i,可以递归解决
// 3. 可以用dp解决吗， 满足最优子结构，dp[i]表示把i分成几个数之和，得到的积最大
// dp[2] = 1 dp[3] = 2 dp[4] = max(dp[1] * dp[3], dp[2] * dp[2]) dp[5] = max(dp[1] * dp[4], dp[2] * dp[3]) ==> dp[1] = 1 ,dp[2] = 2
// 注意dp[1]为1,不然的话，相乘为0了 dp[2] = 2,不能为1!
// dp[3]也是，考虑5 = 2 + 3, 3不该划分了
// 再次思考，如果要把这种分法找出来，怎么办？可以用一个数组把划分的位置记录下来，最后再回溯
// 此题的难点在于定初始值，任何一个数都可以写成1,2,3的和，所以最后必然是分成1,2,3这三种
// 最后都是划分成1,2,3最优解，尽可能多的3,剩下1或者2

public class Lee14_1 {
    public int cuttingRope(int n) {
        if(validParameter(n)) throw  new IllegalArgumentException("n不能小于等于1");
        if(n == 2) return 1;
        if(n == 3) return 3;
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for(int i = 3; i <= n; ++i){
            for(int j = 1; j <= i/2; ++j){
                dp[i] = Math.max(dp[j] * dp[i-j], dp[i]);
            }
        }
        return dp[n];
    }

    boolean validParameter(int n){return n <= 1;}

    public static void main(String[] args) {
        Lee14_1 lee = new Lee14_1();
        System.out.println(lee.cuttingRope(10) == 36);
        // System.out.println(lee.cuttingRope(1) == 1);
        // System.out.println(lee.cuttingRope(2) == 1);
    }

}
